package com.aqie.easy.tree;

import com.aqie.easy.structure.Node;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 559. N叉树的最大深度
 */
public class NTreeMaxDepth {
    /**
     * DFS 深度优先
     * @param root
     * @return
     */
    public int maxDepth(Node root) {
        int depth = 0;
        if (root == null) return depth;
        for (int i  = 0; i < root.children.size(); i++){
            depth = Math.max(depth, maxDepth(root.children.get(i)));
        }
        return depth + 1;
    }

    /**
     * 层序遍历
     */
    public int maxDepth2(Node root) {  //层序遍历解法
        if(root == null)
            return 0;
        if(root.children.size() == 0)
            return 1;
        int depth = 0;
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while(!queue.isEmpty()){
            int count = queue.size();
            depth++;
            while(count > 0){
                Node node = queue.poll();
                if(node.children.size() != 0)
                    queue.addAll(node.children);
                count--;
            }
        }
        return depth;
    }
}
